/*
 *      Author: Guannan Ma
 *      @mythmgn
 *      Whatever license applied
 */

#include <stddef.h>
#include <string.h>

#include "base.h"

BST* initBST(){
    BST *p_bst=(BST *)malloc(sizeof(BST));
    if(NULL==p_bst){
        setErrStatusCode(MEMORY_MALLOC_FAILURE);
        return NULL;
    }
    p_bst->p_left=NULL;
    p_bst->p_right=NULL;
    p_bst->p_data=NULL;
    p_bst->p_key=NULL;
    p_bst->length=0;

    return p_bst;
}




/** \brief
     Function compareData can return 3 different values: -1 0 1 2
     -1 means special things you take, if it returns -1, you have to pass 'specialHandler' to the functions.
     0 means the current p_data is less than the current p_bst->data
     1 means the current p_data is greater than the current p_bst->data
 *
 * \param
 * \param
 * \return 1 if insertion succeed. 0 for the reversely. 2 if the item already exists.
 *
 */

int insertBSTNode(BST* p_bst,char *p_key, void *p_data,int (*compareData)(char *insertKey,char *bstKey),BOOL (*specialHandle)(BST *p_bst,char *p_key)){
    //ASSERT(p_data!=NULL);
	 BST *p_temp=p_bst;

    ASSERT(p_bst!=NULL);
    ASSERT(compareData!=NULL);


    /**< If it's the head node. we will not malloc a new one. We will use it. */
    if(NULL==p_temp->p_data&&NULL==p_temp->p_key){
        p_temp->p_key=(char *)malloc(sizeof(char)*(MAX_LENGTH_OF_KEY+1));
        if(p_temp->p_key==NULL){
            setErrStatusCode(MEMORY_MALLOC_FAILURE);
            return FALSE;
        }
        strcpy(p_temp->p_key,p_key);
        p_temp->p_data=p_data;
        p_temp->length=1;
        return TRUE;
    }

    while(p_temp){
        switch(compareData(p_key,p_temp->p_key)){
            case -1:
                ASSERT(specialHandle!=NULL);
                return specialHandle(p_temp,p_key);
                break;
            case 0:
                if(p_temp->p_left){
                    p_temp=p_temp->p_left;
                }else{
                    p_temp->p_left=(BST *)malloc(sizeof(BST));
                    p_temp=p_temp->p_left;
                    goto normalCheck;
                }
                break;
            case 1:
                if(p_temp->p_right){
                    p_temp=p_temp->p_right;
                }else{
                    p_temp->p_right=(BST *)malloc(sizeof(BST));
                    p_temp=p_temp->p_right;
                    goto normalCheck;
                }
                break;
            case 2:
                setErrStatusCode(ITEM_ALREADY_EXIST);
                return 2;
            default:
                return 0;
        }
    }

normalCheck:
    if(NULL==p_temp){
        setErrStatusCode(MEMORY_MALLOC_FAILURE);
        return 0;
    }
    p_temp->p_left=NULL;
    p_temp->p_right=NULL;
    p_temp->p_key=(char *)malloc(sizeof(char)*(MAX_LENGTH_OF_KEY+1));
    if(p_temp->p_key==NULL){
            setErrStatusCode(MEMORY_MALLOC_FAILURE);
            return 0;
    }
    strcpy(p_temp->p_key,p_key);
    p_temp->p_data=p_data;
    p_bst->length+=1;

    return TRUE;

}

char ** traverseBSTKey(BST *p_bst){

	int i=0;
	stack *p_stack;
	char **p_void;
	BST *p_temp;

    ASSERT(p_bst!=NULL);

    if(p_bst->length==0){
        return NULL;
    }
    p_stack=initStack(p_bst->length,1);
    p_void=(char **)malloc(sizeof(char *)*(p_bst->length));

    if(p_stack==NULL){
        setErrStatusCode(MEMORY_MALLOC_FAILURE);
        return NULL;
    }

    if(p_void==NULL){
        setErrStatusCode(MEMORY_MALLOC_FAILURE);
        FREEUP(p_stack);
        return NULL;
    }


    p_temp=p_bst;
    while(p_temp){
        if(push_in(p_temp,p_stack)!=1){
            freeStack(p_stack);
            FREEUP(p_void);
            return NULL;
        }
        if(p_temp->p_left)
            p_temp=p_temp->p_left;
        else if(p_temp->p_right){
            p_void[i++]=p_temp->p_key;
            pop_up(p_stack);
            p_temp=p_temp->p_right;
        }
        else{
            pop_up(p_stack);
            p_void[i++]=p_temp->p_key;

            for(p_temp=pop_up(p_stack);p_temp!=NULL&&p_temp->p_right==NULL;p_temp=pop_up(p_stack)){
                    p_void[i++]=p_temp->p_key;
            }
            if(NULL==p_temp){
                freeStack(p_stack);
                return p_void;
            }
            else{
                p_void[i++]=p_temp->p_key;
                p_temp=p_temp->p_right;

            }
        }
    }
    return NULL;
}


BOOL closeTraverse(void *p_value){
    FREEUP(p_value);
    return TRUE;
}

BOOL freeBST(BST *p_bst,BOOL(*freeContent)(void *data)){
    ASSERT(p_bst!=NULL);
    if(p_bst->p_left)
        freeBST(p_bst->p_left,freeContent);
    if(p_bst->p_right)
        freeBST(p_bst->p_right,freeContent);
    if(freeContent){
        freeContent(p_bst->p_data);
    }
    FREEUP(p_bst->p_key);
    FREEUP(p_bst);

    return TRUE;
}
